#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAXSIZE 20

/**
 * 数组初始化（生成随机数）
 * @param A
 * @param length
 */
void ArrayInit(int A[], int length) {
    srand(time(NULL));  // 初始化随机种子
    for (int i = 0; i < length && i < MAXSIZE; ++i) {
        A[i] = rand() % 100;
    }
}

/**
 * 打印数组
 * @param A
 * @param length
 */
void ArrayPrint(int A[], int length) {
    for (int i = 0; i < length; ++i) {
        printf("%3d ", A[i]);
    }
    printf("\n");
}

/**
 * 插入排序
 * @param A
 * @param length
 */
void InsertSort(int A[], int length) {
    int i, j, tmp;
    for (i = 1; i < length; ++i) {  // 从第2个元素开始排序
        if (A[i] < A[i-1]) {        // 如果新元素小于前驱（说明要前移）
            tmp = A[i];             // 暂存需要前移的元素
            for (j = i; j > 0 && A[j-1] > tmp; --j) {
                A[j] = A[j-1];      // 将已排序序列中大于目标元素的元素依次后移
            }
            A[j] = tmp;             // 将目标元素放入目标位置
        }
    }
}


int main() {
    printf("Hello, InsertSort!\n");

    int A[MAXSIZE];         // 定义数组
    int length = 10;        // 设置使用的长度

    // 初始化数组生成随机数
    ArrayInit(A, length);
    ArrayPrint(A, length);

    // 插入排序
    InsertSort(A, length);
    ArrayPrint(A, length);

}